package com.chj.lintcode.backpack;

//https://github.com/cherryljr/LintCode/blob/master/Backpack%20VII.java
public class Code07_BackpackVII {

	/*
	 * Description Assume that you have n yuan. There are many kinds of rice in the
	 * supermarket. Each kind of rice is bagged and must be purchased in the whole
	 * bag. Given the weight, price and quantity of each type of rice, find the
	 * maximum weight of rice that you can purchase. Example Given: n = 8 prices =
	 * [2,4] weight = [100,100] amounts = [4,2] Return:400
	 */

	/**
	 * Approach 1: Multiple Backpack 本题属于 多重背包问题。 相比于 01背包 和 完全背包 问题，其实际上只是增加了一个限制条件
	 * --- 每个物品有特定的个数限制。 如果对其他两个背包问题掌握得足够好的话，仅仅是要解决该类问题还是相当简单的。 从 矩阵的递推
	 * 过程出发，新增的条件实际上只是将 dp[i][j] 的状态依赖限制在了某一段特定的区域之中。 因此我们只需要利用 物品个数的限制条件
	 * 来计算出当前状态所依赖的区域即可。
	 *
	 * 以本题为例，dp[i][j] 表示：在前 i 个物品中，花费 j 的金额最多能够买到多少大米。 则其所依赖的状态为：在前 i-1 个物品中，花费
	 * j-k*prices[i] 的金额所能买到最多的大米重量。 即 上一行 中，j-k*prices[i] (0 <= k <= amounts[i] &&
	 * j-k*prices[i] >= 0) 的这段区域 因此：dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - k *
	 * prices[i]] + k * weight[i]) 最终结果为：dp[n - 1][m]
	 *
	 * 时间复杂度：O(N*M*K); 空间复杂度：O(N*M)
	 *
	 * 类似的问题还有： Backpack VIII：
	 * https://github.com/cherryljr/LintCode/edit/master/Backpack%20VIII.java 美丽的项链：
	 * https://github.com/cherryljr/NowCoder/blob/master/%E7%BE%8E%E4%B8%BD%E7%9A%84%E9%A1%B9%E9%93%BE.java
	 */

	/**
	 * @param m: the money of you
	 * @param prices: the price of rice[i]
	 * @param weight: the weight of rice[i]
	 * @param amounts: the amount of rice[i]
	 * @return: the maximum weight
	 */
	public static int backPackVII(int m, int[] prices, int[] weight, int[] amounts) {
		int n = prices.length;
		int[][] dp = new int[n][m + 1];
		// Initialize
		for (int i = 0; i <= amounts[0]; i++) {
			if (i * prices[0] <= m) {
				dp[0][i * prices[0]] = i * weight[0];
			}
		}

		// Function
		for (int i = 1; i < n; i++) {
			for (int j = 0; j <= m; j++) {
				for (int k = 0; k <= amounts[i]; k++) {
					// Guarantee the money is enough to pay k*prices[i]
					if (j >= k * prices[i]) {
						dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - k * prices[i]] + k * weight[i]);
					} else {
						// 如果当前价值超过了总价值 j,那么后面就没有继续计算的必要了
						break;
					}
				}
			}
		}

		// Answer
		return dp[n - 1][m];
	}

	public static int backPackVII02(int n, int[] prices, int[] weight, int[] amounts) {
		int itemCount = prices.length; // count of items
//        vector<vector<int>> dp(itemCount + 1, vector<int>(n + 1, 0)); //dp[i][j] means the maximum weight of first i tems with total price <= j
		int[][] dp = new int[itemCount + 1][n + 1];
		for (int i = 1; i <= itemCount; i++) {
			for (int k = 1; k <= n; ++k) {
				dp[i][k] = dp[i - 1][k];
			}

			for (int j = 0; j <= amounts[i - 1]; j++) {
				for (int k = 1; k <= n; ++k) { // k-> 1 .. n
					if (k >= j * prices[i - 1]) {
						dp[i][k] = Math.max(dp[i][k], dp[i - 1][k - j * prices[i - 1]] + j * weight[i - 1]);
					}
				}
			}
		}

		return dp[itemCount][n];
	}

//	Example 1:
//
//		Input: n = 8, prices = [3,2], weights = [300,160], amounts = [1,6]
//		Output: 640
//		Explanation: Buy the second rice(price = 2) use all 8 money.
//		Example 2:
//
//		Input: n = 8, prices = [2,4], weight = [100,100], amounts = [4,2 ]
//		Output: 400 
//		Explanation: Buy the first rice(price = 2) use all 8 money.
	public static void main(String[] args) {
		{
			int m = 8;
			int[] prices = { 3, 2 };
			int[] weight = { 300, 160 };
			int[] amounts = { 1, 6 };
			System.out.println(backPackVII(m, prices, weight, amounts));
			System.out.println(backPackVII02(m, prices, weight, amounts));
		}

		{
			int m = 8;
			int[] prices = { 2, 4 };
			int[] weight = { 100, 100 };
			int[] amounts = { 4, 2 };
			System.out.println(backPackVII(m, prices, weight, amounts));
			System.out.println(backPackVII02(m, prices, weight, amounts));
		}
	}
}
